package test7;

public class HashBuck {
    static  class Node{
        public int val;
        public int key;
        public Node next;

        public Node(int val, int key) {
            this.val = val;
            this.key = key;
        }
    }

    public Node[] array;
    public int usedSize;
    public static final double DEFAULT_LOADFACTER=0.75;

    public HashBuck(){
        this.array=new Node[10];
    }

    //put函数
    public void put(int key,int val){
        //1.找到key所在的位置
        int index=key % this.array.length;
        //2. 遍历这个下标的链表，看是否有相同的key，有。就要更新val值
        Node cur=array[index];
        while(cur != null){
            if(cur.key==key){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //3.没有这个key这个元素,头插法
        Node node=new Node(key,val);
        node.next=array[index];
        array[index]=node;
        this.usedSize++;

        //4.插入元素成功只够，检查当前散列表的负载因子
        if(loadFacter() >= DEFAULT_LOADFACTER){
            //扩容,不是简单的扩容，还要重新哈希
            resize();
        }
    }
    private void resize(){
        Node[] newArray=new Node[array.length*2];
        for(int i=0;i<array.length;i++){
            Node cur=array[i];
            while(cur != null){
                int index=cur.key % newArray.length;//获取新的下标
                //把cur这个节点以头插或尾插的形式插入到新的数组对应的下标的链表中
                Node curNext=cur.next;
                cur.next=newArray[index];
                newArray[index]=cur;
                cur=curNext;

            }
        }
        array=newArray;
    }

    private double loadFacter(){
        return 1.0*usedSize/array.length;
    }

    //根据key获取val值
    public int get(int key){
        int index=key % array.length;
        Node cur=array[index];
        while(cur != null){
            if(cur.key==key){
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;

    }

    public static void main(String[] args) {
        HashBuck hashBuck=new HashBuck();
        hashBuck.put(1,1);
        hashBuck.put(12,12);
        hashBuck.put(3,3);
        hashBuck.put(6,6);
        hashBuck.put(7,7);
        hashBuck.put(2,2);
        hashBuck.put(11,11);
        hashBuck.put(8,8);
        System.out.println(hashBuck.get(11));
    }
}
